//
// Created by PC on 2017/11/18.
//

#ifndef HEAPSORT_MAXHEAP_H
#define HEAPSORT_MAXHEAP_H

#include <iostream>
#include <cassert>
using namespace std;
template <typename Item>
class MaxHeap{
private:
    Item *data;
    int count;
    int capacity;
    void shiftUp(int k) {
        Item e=data[k];
        while (k > 1 && data[k / 2] < e) {
//            swap(data[k/2],data[k]);
            data[k]=data[k/2];
            k/=2;
        }
        data[k]=e;
    }
    void shiftDown(int k) {
        while (2*k<=count){
            int j=2*k;
            if(j+1<=count && data[j+1]>data[j])
                j+=1;
            if(data[k]>=data[j])
                break;
            swap(data[k],data[j]);
            k=j;
        }
    }
public:
    MaxHeap(int capacity){
        data=new Item[capacity+1];
        count=0;
        this->capacity=capacity;
    }

    MaxHeap(Item arr[],int n){
        data=new Item[n+1];
        capacity=n;
        for(int i=0;i<n;i++)
            data[i+1]=arr[i];
        count=n;
        for(int j=count/2;j>=1;j--)
            shiftDown(j);
    }
    ~MaxHeap(){
        delete[] data;
    }
    int size(){
        return count;
    }
    bool isEmpty(){
        return count==0;
    }

    void insert(Item item) {
        assert(count+1<=capacity);
        data[count+1]=item;
        count++;
        shiftUp(count);
    }

    Item  extractMax(){
        assert(count>0);

        Item ret=data[1];
        swap(data[1],data[count]);
        count--;
        shiftDown(1);
        return ret;
    }
};
#endif //HEAPSORT_MAXHEAP_H
